/*
百度北邮笔试题 

定义中位数为：
2n个有序数，第n个为这个序列的中位数；
2n+1个有序数，第n+1个数为这个序列的中位数。

现给出一个乱序数列，如3、2、5、1、6、9、10、……，求其中位数。 
*/

#include "junix.h"
using namespace std;

template <typename Type>
int partition(Type v[], int beg,int end) {
	assert(end-beg>=2);
	Type x = v[beg];
	int i=beg;
	for (int j=beg+1;j<=end;j++) {
		if (v[j]<x)
			std::swap(v[++i],v[j]);
	}

	std::swap(v[beg],v[--i]);
	return i+1;
}

template <typename Type> 
Type expect(Type v[],int beg,int end, int pos) 
{
	assert(beg<=pos);
	assert(pos<=end);

	if (beg==end) 
		return v[pos];

	if (end-beg==2) {
		if (v[beg]>v[end])
			std::swap(v[beg],v[end]);
		return v[pos];
	}

	int index=partition(v,beg,end);
	if (index==pos) {
		return v[pos];
	} else if (index<pos) {
		return expect(v,index+1,end,pos);
	} else {
		return expect(v,beg,index-1,pos);
	}
}

int main(int argc, char **argv)
{
	const int sz = 10000;
	int v[sz];
	for (int i=0;i<sz;i++)
		v[i]=i;

	std::random_shuffle(v,v+sz);

	std::cout<<expect(v,0,sz-1,666);
}
